package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	list1 := findPath(root, p)
	list2 := findPath(root, q)
	for _, n1 := range list1 {
		for _, n2 := range list2 {
			if n1 == n2 {
				return n1
			}
		}
	}
	return nil
}

type MyNode struct {
	tree   *TreeNode
	parent *MyNode
}

func findPath(root, p *TreeNode) []*TreeNode {
	root1 := &MyNode{
		tree: root,
	}
	stack := []*MyNode{root1}
	for len(stack) > 0 {
		head := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		if head.tree == p {
			result := make([]*TreeNode, 0)
			// var result []*TreeNode
			n := head
			for n != nil {
				result = append(result, n.tree)
				n = n.parent
			}
			return result
		}
		if head.tree.Left != nil {
			stack = append(stack, &MyNode{tree: head.tree.Left, parent: head})
		}
		if head.tree.Right != nil {
			stack = append(stack, &MyNode{tree: head.tree.Right, parent: head})
		}
	}
	return nil
}

func main() {
	n0 := &TreeNode{Val: 3}
	n1 := &TreeNode{Val: 5}
	n2 := &TreeNode{Val: 1}
	n3 := &TreeNode{Val: 6}
	n4 := &TreeNode{Val: 2}
	n5 := &TreeNode{Val: 7}
	n6 := &TreeNode{Val: 4}
	n0.Left = n1
	n0.Right = n2
	n1.Left = n3
	n1.Right = n4
	n4.Left = n5
	n4.Right = n6
	result := lowestCommonAncestor(n0, n1, n6)
	println(result)
}
